package com.kevinkk.dp;

/**
 * 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
 * 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
 *
 * 1. dp 数组的含义：dp[i][j] 字符串中以 i 和 j 结尾的回文子串的长度
 * 2. dp 公式：
 *      if (c[i] == c[j]) {
 *          dp[i][j] = dp[i + 1][j - 1] + 2;                ---> 不需要操作，那么长度加二
 *      } else {
 *          dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);---> 尝试删除一个元素
 *      }
 * 3. 初始化：显然 每个字符串以自己为中心的字符串为回文串，长度为1
 * 4. 遍历顺序：必须优先保证 dp[i + 1][j - 1] 被计算了，因此 i 倒序遍历，j 正序遍历
 */

public class LongestPalindromicSubsequence {
    class Solution {
        public int longestPalindromeSubseq(String s) {
            char[] c = s.toCharArray();
            int res = 1;
            int[][] dp = new int[c.length][c.length];
            for (int i = 0; i < c.length; i++)
                dp[i][i] = 1;

            for (int i = c.length - 1; i >= 0; i--) {
                for (int j = i + 1; j < c.length; j++) {
                    if (c[i] == c[j]) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    } else {
                        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                    }
                    res = Math.max(res, dp[i][j]);
                }
            }

            return res;
        }
    }
}
